Digital signature nowadays is a basic technology in the field of network communication security. Digital signature uses Asymmetric Cryptography Algorithm to assure that others may verify the digital signature but cannot personate it. The most popular asymmetric algorithms are RSA, DSA and Elliptical Curve Algorithm etc. At present, many digital signature systems are based on RSA (Ron Rivest, Adi Shamir and Len Adleman Algorithm) algorithm.
The asymmetric algorithm is that the reverse computation parameter cannot be derived from the known computation parameters, i.e. while the computation procedure is known, yet it has no computation ability to do reverse computation. The asymmetric algorithm is publicized, everyone can select his own parameters, and different parameters will result in different constituted transformation functions. One may select a group of parameters, some of them used for reverse computation are called secret parameters, technically called secret key or private key; the others used for computation are called public parameters or public key.
Implementation of the digital signature is based on the asymmetric algorithm. On the one hand, the self-possessed secret parameter-private key is protected, which will assure that no one can forge the digital signature; on the other hand, by publicizing what could be put to publicity—the public key, verification of the signature could be carried out for certain people. In fact, deriving secret parameters from public parameters are computationally infeasible theoretically.
First of all, digital signature guarantees the security of network communication and interaction, and it ensures that the counterpart of the communication is authentic and that it is yourself that is on line; at the same time digital signature can be used as a tool for signing electronic documents in order to protect the self-possessed documents and signatures. Today, in many countries, digital signature has already been considered the same as manual signature, and both of them have the same legal effect.
Digital signature algorithms can also be used for negotiation of secret parameters. Suppose user A needs to communicate with user B secretly, then, user A defines secret parameters and encrypts them with user B's public key. By this means, only user B can decrypt the encrypted secret parameters, since only user B knows his own private key.
Besides, digital signature can also be used in cases where confidentiality authentication or non-repudiation is required.
The Public Key Infrastructure (PKI) that has been popular worldwide is a kind of application for digital signature. PKI is a vital infrastructure for a digital society as the importance of the electricity infrastructure for the industrial society.
To ensure security and speed of digital signatures, before signing, the content to be signed has to be hashed using a message digest function to get a hashed value, sometimes called digest value, M, and then the signature value will be obtained by encrypting the digest value with the private key. When verifying a signature, first a hash computation is made and then the public key decrypts the signature value; then the obtained result is compared with the above hashed result, if they are equal to each other, the signature is correct, otherwise the verification cannot be passed.
Nevertheless, suppose that user A has a private key and a public key, and there is an attacker B who regenerates a private key and a public key and replaces user A's public key with his own public key (the attacker B's public key). In this case, encrypted messages sent to user A by his friend will only be decrypted by attacker B, for user A does not know the corresponding private key of the forged public key of attacker B. At this time, it is highly demanded to have a Certificate Authority (CA) to verify which public key belongs to user A or to prove which public key does not belong to user A.
CA has a longer private key than that of the common users, i.e. the CA private key is more secure, and the CA public key is well-known by various ways publicly. Thus, every user can verify which is signed and issued by CA. When user's identity is attached with the user's public key and signed by CA, the user gets a digital certificate, which proves the identity of the legitimate owner of the public key. Further more, everyone can verify a digital certificate, but no one can forge a digital certificate.
At present, the digital certificate is the most pivotal part of PKI, while CA is the key unit in PKI. With the help of the digital certificate, security of a network, such as confidentiality, integrity, non-repudiation etc, can be solved effectively.
Security based on PKI eventually will be focused on the security of the CA's private key. Once the CA's private key is compromised, all certificates issued by the CA must be revoked and the network security controlled by the CA will be compromised. Along with the increasing of various means of network attacks, system vulnerabilities constantly be discovered, so it becomes a crucial topic of modern network security researches to insure security of online digital signature service.
For RSA, secret-key usually is noted as d that can be an integer as long as 2048 bits. Generally speaking, a private key with 1024 bits in length is enough to assure security, but for CA's, with the length of 2048 bits or even longer is recommended. The RSA uses the computation of modular exponentiation of a number N i.e. calculating expression Md mod N, the computation is necessary for a digital signature. When the public key is publicized, protecting the integer d is to protect the private key.
The purposes of a secure digital signature is to fulfill signing but without compromising the private key. According to this subject, many theoretical researches have been carried out in the world, while some of the theories and methods are too difficult to implement due to the complexity. On the other hand, present development of PKI is focused on producing compatible digital signature products, but little development has made on aspect of secure signature with intrusion tolerance ability. So-called intrusion tolerance is relative to the intrusion detection to guarantee CA security; that is, even when part of a system has been attacked or occupied, secret information of the CA system will not be compromised.
In summary, PKI is based on public key algorithm, and CA is a trusted center of a domain in a PKI system. Communication and authentication between devices or individuals on a network depends on a digital certificate signed and issued by a CA. A digital certificate is data obtained by attaching a public key to the personal identity and then signed with the private key of a CA. When one side of a communicator wants to verify the identity of the other side, there are two steps: first, verifying whether the signature of the certificate of the other side is correct or not, for the signature can only be produced by the CA private key; and then verifying whether the other side has the private key corresponding to the public key in the certificate. If these two steps are performed successfully, then the identity of the other side is determined and trustworthy.
Therefore, the CA private key is the core part of CA security. So to protect it from compromising is the foundation of the security of the entire CA domain. In general, CA has to be an online network device, especially the one that gets direct connection with users to provide corresponding certificate services, thus it is unavoidable to be attacked. When a hacker attacked a CA successfully, he might acquire internal resource of the CA, consequently the CA private key, and this would cause fatal damage to the PKI system. Meanwhile as a precaution, it should be assured that employee working for PKI who has got entire control of some components of a CA system cannot get the CA private key either.
In the following paragraphs, suppose that a digital signature is equivalent to implementing expression Md mod N, wherein d is a private key, and several existing methods for security digital signature are described.
Reference to FIG. 1, this is a prototype system diagram of ITTC project at US Stanford University. The system implements intrusion tolerance through threshold cryptography technology. There are clients, servers and an administrator in the system. The Web Server of the clients refers to the web server that requests signatures and CA is the certificate authority. The servers include multiple share-servers, called as share calculators or share operators, which are responsible for producing the secure digital signatures, as the share-server 1 to share-server 3 in FIG. 1. The administrator is an optional device used to manage the share servers. Features of the scheme are simple configuration and high security, in this system a single layer structure with multiple share-servers is used.
Principle for the system to achieve security is to first divide a private key d into a sum of t numbers: d=d1+d2+ . . . +dt, and then each number di is allocated to every share-server accordingly. When a signature is necessary, the client, a web or a CA, sends the information of a HASH value M that needs to be signed to every share-server; and then every share-server returns the computation result Mi=Mdi to the client, a web or a CA, accordingly. The client then makes multiplication:
  S  =                    ∏                  i          =          1                t            ⁢              M                  d          i                      =                  M                              ∑                          i              =              1                        t                    ⁢                      d            i                              =              M        d                            And the result needed is obtained.        
To implement redundancy, multiple groups of the equations can be further used to implement redundancy configuration, i.e. taking several groups of the d division randomly, such as:                First group: d=d11+d12+ . . . +d1t;        Second group: d=d21+d22+ . . . +d2t;        
Then, the numbers of multiple groups (dij) are allocated to different share-servers in the way that every share-server can obtain multiple dij, but can only obtain one data of the same group, for example share-server 1 obtains d11 from the first group and d23 from the second group. For instance, suppose there are four share-servers and t=3, the allocation can be as in the following table:
Share-server 1Share-server 2Share-server 3Share-server 4d11d12d13d13d23d21d22d23
When a client, a Web or a CA, wants to compute the signature, the client selects t perfect share-servers and tells the share-servers which group of the data or parameters should be used, and then the share-servers can compute the according signature.
Advantages of this scheme are obvious, but the disadvantages are as follows.                1. It is difficult to allocate and manage sub-secret-keys. Whenever adding a share-server, the sub-secret-keys must be allocated for every online share-server and also the adding of the new share-server must be known by clients.        2. When there are many share-servers, the storage capacity for sub-secret-keys will be rapidly increased. Suppose the total number of share-servers is k, and the required number of the perfect share-servers is t, then the number of stored sub-secret-keys for each share-server is at least Ckt−1, wherein C represents combination. When k=10 and t=3, each share-server has to store 45 sub-secret-keys.        3. There is a synchronization problem that must be solved at first. Before computation, the client must select t share-servers, then find out data groups matching to the t share-servers and inform them; once one of the t share-servers has been destroyed, the above selecting procedure must be repeated.        4. It is difficult for the client (CA or Web server) to remember every change made by the share-servers, it is not easy to manage or extent, especially when the client is online, it is more difficult to extend so that updating the data of client is necessary whenever the share-servers' parameters change.        
Victor Shoup at IBM Research Zurich Institute has released an article titled “Practical Threshold Signatures” on Europe Cryptography Annual Meeting in the Year 2000, what the article introduces is a theoretical scheme on digital signature. The scheme employs RSA algorithm with strong prime, primes kept in secret are p=2p′+1 and q=2q′+1. All interpolation equations are made in the ring of mod m=p′q′. Since M4m mod N is equal to 1, when computation is separate, one more square operation is needed. This is performed by the Combiner that takes a square operation to each result respectively, to obtain M4(gm+d), wherein Δ=(k!)2 and g is an integer. In this scheme, CA is performed by the combiner, so the synchronization problem before computation is eliminated, but it increases computation difficulties and decreases computation performance of the combiner. For example, the combiner must compute following formula:
  W  =            y              i        1                    2        ⁢                                  ⁢        λ        ⁢                                  ⁢                  c                      i            1                                ⁢          y              i        2                    2        ⁢                                  ⁢        λ        ⁢                                  ⁢                  c                      i            2                                ⁢                  ⁢    …    ⁢                  ⁢          y              i        t                    2        ⁢                                  ⁢        λ        ⁢                                  ⁢                  c                      i            t                              wherein yi is the computation result of each share-server and λ=k!.
It can be seen that the features and disadvantages of this scheme lie in:                1. It is still a single layer sharing structure consisted of share-servers, the combiner does not store any secret information, so any device can fulfill the combination work.        2. Computation volume of the combiner is approximate to or equal to that of signing for t times, this computation volume is far more than that of the share-servers, so even if the algorithm can be implemented, the scheme cannot be used in practical signing.        3. It is required to use strong primes, which will bring about limitation for some applications.        4. It is only described theoretically that other devices will not be affected when increasing or deleting a share-server; yet, the description only provides mathematical formula with no explanation on implementation or system structure.        
Yair Frankel et al in CertCo Company in New York has brought forward a scheme but without implementation diagram or any details of the system. In this scheme, it is proposed that polynomial coefficients ai is in {0, L, . . . ,2L3N2+et}, wherein L=k!, and xi belongs to [1,2, . . . , k−1]. Since all f(xi) can be divided by L, so bi computation is without reverse operation and can be made in the integer domain. The scheme may apply the general RSA algorithm without the requirement of strong prime. Nevertheless, as parameter selection is greatly limited, so algorithm principle and proving of security becomes complicated. When a share-server computes bi, the synchronization problem also exists for bi depends on the selection of xi.
From the mathematical description, the scheme has the following disadvantages:                1. A secret-key is shared equally, that is, the share is a single layer structure.        2. Selection of parameters is limited and prove of security is complicated, so possibility of loophole occurring is increased.        3. The synchronization problem exists and if taking away synchronization, computation volume of the combiner will be greatly increased.        
The schemes of IBM Research—Zurich Institute and CertCo Company are all based on the Shamir scheme of sharing secret-key using LaGrange interpolation equation. In the original Shamir secret sharing scheme, a secret-key can be generated by taking t shared secret-keys randomly. But in the original Shamir scheme, the secret-key has to be recovered first and this is unexpected for any scheme, for above all the signature security must assure that it is impossible to recover the secret-key in any device.
Basic principle of Shamir scheme of sharing secret-key is as follows:                Give a polynomial        
            f      ⁡              (        x        )              =                  ∑                  i          =          0                          t          -          1                    ⁢                        a          i                ⁢                  x          i                      ,with Lagrange interpolation formula there is:
                              f          ⁡                      (            x            )                          =                              ∑                          i              =              1                        t                    ⁢                      (                                          f                ⁡                                  (                                      x                    i                                    )                                            ⁢                                                ∏                                                            j                      =                      1                                        ,                    t                                                        j                    ≠                    i                                                  ⁢                                                      x                    -                                          x                      j                                                                                                  x                      i                                        -                                          x                      j                                                                                            )                                              (        1        )                            Select t individual items of xi and f(xi), it can be obtained that:        
                              a          0                =                              f            ⁡                          (              0              )                                =                                    ∑                              i                =                1                            t                        ⁢                          (                                                f                  ⁡                                      (                                          x                      i                                        )                                                  ⁢                                                      ∏                                                                  j                        =                        1                                            ,                      t                                                              j                      ≠                      i                                                        ⁢                                                            -                                              x                        j                                                                                                            x                        i                                            -                                              x                        j                                                                                                        )                                                          (        2        )                            a0 can be set as a secret-key, in this case the signature computation of a hash value M is:        
                              M          d                =                              M                          f              ⁡                              (                0                )                                              =                                                    ∏                                  i                  =                  1                                t                            ⁢                              M                                                      f                    ⁡                                          (                                              x                        i                                            )                                                        ⁢                                                            ∏                                                                        j                          =                          1                                                ,                        t                                                                    j                        ≠                        i                                                              ⁢                                                                  -                                                  x                          j                                                                                                                      x                          i                                                -                                                  x                          j                                                                                                                                          =                                          ∏                                  i                  =                  1                                t                            ⁢                              M                                  b                  i                                                                                        (        3        )                                          wherein          ⁢                                          ⁢                      b            i                          =                                            f              ⁡                              (                                  x                  i                                )                                      *                          c              i                                =                                    f              ⁡                              (                                  x                  i                                )                                      ⁢                                          ∏                                                      j                    =                    1                                    ,                  t                                                  j                  ≠                  i                                            ⁢                                                -                                      x                    j                                                                                        x                    i                                    -                                      x                    j                                                                                                          (        4        )            
Therefore, secret-key d can be divided into k share-servers, with k≧t. Each share-server computes Mbi, then a combiner multiplies computation results of every share-server to obtain the Md. In this case, any share-server does not leak the secret-key d. Since there are division operations in formula (4), it is easy to be considered to find a domain or ring Zv for the computation. Here, it must be satisfied that v is a prime number, or v and the determinant of t order Vandermonde array consisted of xi are relative primes.
In general situation, computing Mbi separately will bring a consequence that multiplication
            ∏              i        =        1            t        ⁢          M              b        i              =      M          d      +      wv      is needed. About how to take away the affection of v, many people thinks about the φ(N) for the reason that Mφ(N)=1. When v=φ(N) is taken, selection of xi is greatly limited by the above condition. Furthermore, when an element ∘ and its φ(N) inverse ∘−1 are known, the φ(N) can be obtained, so it is obviously unsafe.
Therefore, theoretically the above schemes have evident disadvantages and there are a lot of problems that need solving before the practical application.